vector 底层原理和扩容过程

1. 底层原理

• vector 是 C++ 标准库中的一个容器，可以看作是一个 动态数组 ，它的大小可以根据元素的增加而增长。它通过在堆上分配一段 连续的内存空间存放元素 ，支持时间复杂度为 O（1 ) 的随机访问。
• vector 底层维护了三个 迭代器 和两个变量，这三个迭代器分别指向对象的起始字节位置，最后一个元素的末尾字节和整个 vector 分配空间的末尾字节。两个变量分别是 size 和 capacity ， Size 表示当前存储元素的数量， capacity 表示当前分配空间的大小。当创建一个 vector 对象时，会分配一个初始化大小的空间存放元素，初始化空间可以通过构造函数的参数指定，缺省情况下为 0 。当对 vector 容器进行增加和删除元素时，只需要调整末尾元素指针，而不需要移动整个内存块。

1. 扩容机制

• 当添加元素的数量达到当前分配空间的大小时， vector 会申请一个更大的内存块，然后将元素从旧的内存块拷贝到新的内存块中，并释放旧的内存块。 扩容可能导致原有迭代器和指针失效，扩容完成后，容器返回指向新内存区域的迭代器或指针。
• vector 扩容的机制分为固定扩容和加倍扩容。
  • 固定扩容就是在每次扩容时在原容量的基础上增加固定容量。但是固定扩容可能会面临多次扩容(扩容的不够大)的情况，时间复杂度较高。
  • 加倍扩容就是在每次扩容时原容量翻倍，优点是使得正常情况下扩容的次数大大减少，时间复杂度低，缺点是空间利用率低。